package org.example.code.test2025.one_month;

import org.example.code.test2024.eight_mouth.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Title: test0109
 * @Author yxy
 * @Package org.example.code.test2025.one_month
 * @Date 2025/1/9 13:36
 * @description:
 */
public class test0109 {
    public List<Integer> grayCode(int n) {
        List<Integer> list = new ArrayList<Integer>();
        list.add(0);
        list.add(1);
        list = fun(n, 2, list);
        return list;

    }

    private List<Integer> fun(int n, int x, List<Integer> list) {
        if (x > n) {
            return list;
        }
        List<Integer> item = new ArrayList<>();
        for (int i = list.size() - 1; i >= 0; i--) {
            item.add((int) (list.get(i) + Math.pow(2, x - 1)));
        }
        list.addAll(item);
        return fun(n, x + 1, list);
    }

    public int numDecodings(String s) {
        if (s.isEmpty() || s.charAt(0) == '0') {
            return 0;
        }
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= s.length(); i++) {
            if (s.charAt(i - 1) != '0') {
                dp[i] = dp[i] + dp[i - 1];
            }
            int twoDigit = Integer.parseInt(s.substring(i - 2, i));
            if (twoDigit > 9 && twoDigit < 27) {
                dp[i] = dp[i] + dp[i - 2];
            }
        }
        return dp[s.length()];
    }

//    public List<String> restoreIpAddresses(String s) {
//        List<String> result = new ArrayList<>();
//        if (s.length() < 4 || s.length() > 12) {
//            return result;
//        }
//        for (int i = 1; i < s.length() && i < 4; i++) {
//            for (int j = i + 1; j < s.length() && j < i + 4; j++) {
//                for (int k = j + 1; k < s.length() && k < j + 4; k++) {
//                    String part1 = s.substring(0, i);
//                    String part2 = s.substring(i, j);
//                    String part3 = s.substring(j, k);
//                    String part4 = s.substring(k);
//                    if (isValid(part1) && isValid(part2) && isValid(part3) && isValid(part4)) {
//                        result.add(part1 + "." + part2 + "." + part3 + "." + part4);
//                    }
//                }
//            }
//        }
//
//        return result;
//    }

    private boolean isValid(String part) {
        if (part.length() > 1 && part.charAt(0) == '0') {
            return false;
        }
        int num = Integer.parseInt(part);
        return num >= 0 && num <= 255;
    }

    public List<String> restoreIpAddresses(String s) {
        if (s.length() < 4 || s.length() > 12) {
            return new ArrayList<>();
        }
        List<String> list = new ArrayList<>();
        List<String> cur = new ArrayList<>();
        funIdp(list, s, cur, 0);
        return list;
    }

    private void funIdp(List<String> list, String s, List<String> cur, int start) {
        if (cur.size() == 4) {
            if (start == s.length()) {
                list.add(String.join(".", cur));
            }
            return;
        }
        for (int i = 1; i <= 3; i++) {
            if (start + i > s.length()) {
                break;
            }
            String str = s.substring(start, start + i);
            if (isValid(str)) {
                cur.add(str);
                funIdp(list, s, cur, i + start);
                cur.remove(cur.size() - 1);
            }
        }

    }

    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }
        return funTree(1, n);
    }

    private List<TreeNode> funTree(int start, int end) {
        List<TreeNode> res = new ArrayList<>();
        if (start > end) {
            res.add(null);
            return res;
        }
        for (int i = start; i <= end; i++) {
            List<TreeNode> lefts = funTree(start, i - 1);
            List<TreeNode> rights = funTree(i + 1, end);
            for (TreeNode left : lefts) {
                for (TreeNode right : rights) {
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    res.add(root);
                }
            }
        }
        return res;
    }


    public static void main(String[] args) {
        test0109 test = new test0109();
        System.out.println(test.generateTrees(3));
    }
}
